// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口中相应字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0; // 左闭右开区间

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移除窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}

// ------------------------------------------------------------------

void slidingWindow(string s)
{
	// 窗口中相应字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0; // 左闭右开区间

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....
		
		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内的一系列更新
			....
		}
	}
}


// -------------------------------------------------------------

void slidingWindow(string s)
{
	// 窗口中相关字符的出现次数
	unordered_map<char, int> window;
	
	int left = 0, right = 0; // 左闭右开区间

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];
		
		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}

// --------------------------------------------------
// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口中相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];
		
		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....
			
		// 判断左侧窗口是不是要收缩
		while(window needs shrink)
		{
			// d是 将移除窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}


// -------------------------------------------------------
// 滑动窗口算法框架：
void slindingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

 	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移除窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....

		}
	}
}

// -------------------------------------------------------
// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口中相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}

// --------------------------------------------------------
// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口中相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];
		
		// 增大窗口
		right++;

		// 进行窗口内数据的交互
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的交互
			....
		}
	}
}

// ---------------------------------------------------------

// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列交互
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列交互
			....
		}
	}
}


// ----------------------------------------------------------

// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列交互
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}

// -------------------------------------------------------

// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0. right = 0;

	while(right < s.size())
	{
		// c是 将移出窗口的字符
		char c = s[right];
		
		// 增大窗口
		right++;

		// 进行窗口内数据的一系列交互
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列交互
			....
		}
	}
}

// ----------------------------------------------------

void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移出窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列交互
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列交互
			....
		}
	}
}

// ---------------------------------------------------

// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];
	
		// 增大窗口
		right++;

		// 进行窗口内数据的一系列交互
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列交互
			....
		}
	}
}

// ---------------------------------------------------

void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列交互
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将要移除窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列交互
			....
		}
	}
}

// --------------------------------------------------------


void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移入窗口的数据
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列交互
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列交互
			....
		}
	}
}


// 最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        unordered_map<char, int> need, window; // 需要凑齐的字符和窗口中相关字符的出现次数

        for(auto c : t) need[c]++;

        int left = 0, right = 0;

        // valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size 的大小相同，则说明窗口已经满足条件，已经完全覆盖了串T

        int valid = 0;

        // 记录最小覆盖子串的起始索引和长度
        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            // c是 将移入窗口的字符
            char c = s[right];

            // 扩大窗口
            right++;

            // 进行窗口内数据的一系列更新
            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                    valid++;
            }

            // 判断左侧窗口是否要收缩
            while(valid == need.size())
            {
                // 在这里更新最小覆盖子串
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                // d是 将移出窗口的字符
                char d = s[left];

                // 缩小窗口
                left++;

                // 进行窗口内数据的一系列更新
                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};
// class Solution {
// public:
//     string minWindow(string s, string t) 
//     {
//         // need和window相当于计数器，分别记录
//         // T中字符出现次数 和 窗口中相应字符的出现次数
//         unordered_map<char, int> window, need;// 记录窗口的字符和需要凑齐的字符
//         for (char c : t) need[c]++;

//         int left = 0, right = 0;
//         // valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T
//         int valid = 0;
//         // 记录最小覆盖子串的起始索引及长度
//         int start = 0, len = INT_MAX;
//         while (right < s.size()) 
//         {
//             // c是 将移入窗口的字符
//             char c = s[right];
//             // 扩大窗口
//             right++;
//             // 进行窗口内数据的一系列更新
//             if (need.count(c)) 
//             {
//                 window[c]++;
//                 if (window[c] == need[c])
//                     valid++;
//             }

//             // 判断左侧窗口是否要收缩
//             while (valid == need.size()) 
//             {
//                 // 在这里更新最小覆盖子串
//                 if (right - left < len) 
//                 {
//                     start = left;
//                     len = right - left;
//                 }
//                 // d是 将移出窗口的字符
//                 char d = s[left];
//                 // 缩小窗口
//                 left++;
//                 // 进行窗口内数据的一系列更新
//                 if (need.count(d)) 
//                 {
//                     if (window[d] == need[d])
//                         valid--;
//                     window[d]--;
//                 }                    
//             }
//         }
//         // 返回最小覆盖子串
//         return len == INT_MAX ?
//             "" : s.substr(start, len); // substr()字符截取函数，从start位置开始截取len个字符
//     }

// };



// 最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        // 需要凑齐的字符和窗口中相关字符的出现次数
        unordered_map<char, int> need, window;

        for(auto c : t) need[c]++;

        int left = 0, right = 0;

        // valid变量表示窗口中满足 need 条件的字符个数（不会重复吗？）
        // 如果valid和need.size()大小相同，则说明窗口已经满足条件，已经完全覆盖了串T
        int valid = 0;

        // 记录最小覆盖子串的起始索引和长度
        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            // c是 将移入窗口的字符
            char c = s[right];

            // 增大窗口
            right++;

            // 进行窗口内数据的一系列更新
            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                    valid++;
            }

            // 判断左侧窗口是否要收缩
            while(valid == need.size())
            {
                // 在这里更新最小覆盖子串
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                // d是 将移出窗口的字符
                char d = s[left];

                // 缩小窗口
                left++;

                // 进行窗口内数据的一系列更新
                if(need.count(d))
                {
                    // 注意顺序
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        // 返回最小覆盖子串
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};


class Solution {
public:
    string minWindow(string s, string t) 
    {
        // 记录需要凑齐的字符和窗口中相关字符的出现次数
        unordered_map<char, int> need, window;

        for(char c : t) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        // 记录最小覆盖子串的起始索引和长度
        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            // c是 将要移入窗口的字符
            char c = s[right];

            // 增大窗口
            right++;

            // 进行窗口内数据的一系列更新
            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                    valid++;
            }

            // 判断左侧窗口是否要收缩
            while(valid == need.size())
            {
                // 在这里更新最小覆盖子串
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                // d是 将移出窗口的字符
                char d = s[left];

                // 缩小窗口
                left++;

                // 进行窗口内数据的一系列更新
                if(need.count(d))
                {
                    if(need[d] == window[d])
                    {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};


// 滑动窗口算法框架
void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}


// ------------------------------------------------------

// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将要移入窗口内的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将要移除窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....

		}
	}
}

// ---------------------------------------------------------------------


// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口内相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将要移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将要移出窗口的数据
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}

// ------------------------------------------------------------------

// 最小覆盖子串 - 困难题
class Solution {
public:
    string minWindow(string s, string t) 
    {
        // 记录窗口内相关字符的出现次数 和 需要凑齐的字符的出现次数
        unordered_map<char, int> window, need;

        for(char c : t) need[c]++;

        int left = 0, right = 0;

        // 窗口中的字符满足T中字符的个数，当valid值等于need.size时说明窗口中的字符全部满足T了， 此时已然是一个可行解，可以缩小左侧窗口寻找最优解
        int valid = 0;

        // 标定最小覆盖子串的起始位置及长度
        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            // c是 将要移入窗口的字符
            char c = s[right];

            // 增大窗口
            right++;

            // 进行窗口内数据的一系列更新
            if(need.count(c)) // 当移入窗口的字符在T中时
            {
                window[c]++;

                if(window[c] == need[c]) // 当窗口中某满足条件的字符的出现次数和T中该字符的出现次数一致时，需要将valid++
                    valid++;
            }

            // 判断左侧窗口是否要收缩
            // 左侧窗口收缩的条件是valid的值等于need.size（表示窗口中满足条件的字符的出现次数都和T中的一致）
            while(valid == need.size())
            {
                // 此处更新最小覆盖窗口的起始位置和长度
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                // d是 将要移出窗口的元素
                char d = s[left];

                // 缩小窗口
                left++;

                // 进行窗口内数据的一系列更新
                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        valid--;
                    }

                    window[d]--;
                }
            }

        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};
// class Solution {
// public:
//     string minWindow(string s, string t) 
//     {
//         // need和window相当于计数器，分别记录
//         // T中字符出现次数 和 窗口中相应字符的出现次数
//         unordered_map<char, int> window, need;// 记录窗口的字符和需要凑齐的字符
//         for (char c : t) need[c]++;

//         int left = 0, right = 0;
//         // valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T
//         int valid = 0;
//         // 记录最小覆盖子串的起始索引及长度
//         int start = 0, len = INT_MAX;
//         while (right < s.size()) 
//         {
//             // c是 将移入窗口的字符
//             char c = s[right];
//             // 扩大窗口
//             right++;
//             // 进行窗口内数据的一系列更新
//             if (need.count(c)) 
//             {
//                 window[c]++;
//                 if (window[c] == need[c])
//                     valid++;
//             }

//             // 判断左侧窗口是否要收缩
//             while (valid == need.size()) 
//             {
//                 // 在这里更新最小覆盖子串
//                 if (right - left < len) 
//                 {
//                     start = left;
//                     len = right - left;
//                 }
//                 // d是 将移出窗口的字符
//                 char d = s[left];
//                 // 缩小窗口
//                 left++;
//                 // 判断左侧窗口是否要收缩
                   // 左侧窗口收缩的条件是valid的值等于need.size（表示窗口中满足条件的字符的出现次数都和T中的一致）
//                 if (need.count(d)) 
//                 {
//                     if (window[d] == need[d])
//                         valid--;
//                     window[d]--;
//                 }                    
//             }
//         }
//         // 返回最小覆盖子串
//         return len == INT_MAX ?
//             "" : s.substr(start, len); // substr()字符截取函数，从start位置开始截取len个字符
//     }

// };



// 字符串的排列 -- 中等题
class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        // 相当于问我们：
        // 有字符串S和字符串T，问S中是否有一个子串，包含T中所有字符且不含其它字符

        unordered_map<char, int> window, need;

        for(char c : s1) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }

        return false;
    }
};


// 找到字符串中所有字母异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        unordered_map<char, int> window, need;

        for(char c : p) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        vector<int> res; // 用于记录结果

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= p.size())
            {
                if(valid == need.size())
                    res.push_back(left);

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }
        return res;

    }
};


// 滑动窗口算法框架：
void slidingWindow(string s)
{
	// 窗口中相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将要移入窗口的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断是否要缩小窗口
		while(window needs shrink)
		{
			// d是 将要移出窗口的字符
			char d = s[left};

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
			
		}
	}
}


// 最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        // 记录窗口内相关字符的出现次数 和 需要凑齐的字符的出现次数
        unordered_map<char, int> window, need;

        for(char c : t) need[c]++;

        int left = 0, right = 0;

        // 窗口内某字符满足T中的要求，并且出现次数也一致时，valid++
        // 如果valid==need.size的大小，说明窗口中的字符有了可行解，接下来收缩左侧窗口，
        // 寻找最优解
        int valid = 0;

        // 用于标定最小子串的起始位置 和 长度
        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            // c是 将要移入窗口的字符
            char c = s[right];

            // 增大窗口
            right++;

            // 进行窗口内数据的一系列更新
            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            // 判断左侧窗口是否要收缩
            while(valid == need.size())
            {
                // 此处需要标记最小覆盖子串的起始位置和长度
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                // d是 将要移出窗口的字符
                char d = s[left];

                // 缩小窗口
                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};
// class Solution {
// public:
//     string minWindow(string s, string t) 
//     {
//         // need和window相当于计数器，分别记录
//         // T中字符出现次数 和 窗口中相应字符的出现次数
//         unordered_map<char, int> window, need;// 记录窗口的字符和需要凑齐的字符
//         for (char c : t) need[c]++;

//         int left = 0, right = 0;
//         // valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T
//         int valid = 0;
//         // 记录最小覆盖子串的起始索引及长度
//         int start = 0, len = INT_MAX;
//         while (right < s.size()) 
//         {
//             // c是 将移入窗口的字符
//             char c = s[right];
//             // 扩大窗口
//             right++;
//             // 进行窗口内数据的一系列更新
//             if (need.count(c)) 
//             {
//                 window[c]++;
//                 if (window[c] == need[c])
//                     valid++;
//             }

//             // 判断左侧窗口是否要收缩
//             while (valid == need.size()) 
//             {
//                 // 在这里更新最小覆盖子串
//                 if (right - left/*左闭右开，right多走一个位置*/ < len) // 这一步很重要，找最优解用的
//                 {
//                     start = left;
//                     len = right - left;
//                 }
//                 // d是 将移出窗口的字符
//                 char d = s[left];
//                 // 缩小窗口
//                 left++;
//                 // 判断左侧窗口是否要收缩
                   // 左侧窗口收缩的条件是valid的值等于need.size（表示窗口中满足条件的字符的出现次数都和T中的一致）
//                 if (need.count(d)) 
//                 {
//                     if (window[d] == need[d])
//                         valid--;
//                     window[d]--;
//                 }                    
//             }
//         }
//         // 返回最小覆盖子串
//         return len == INT_MAX ?
//             "" : s.substr(start, len); // substr()字符截取函数，从start位置开始截取len个字符
//     }

// };

	
// 字符串的排列
class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        // 相当于问我们：
        // 给定字符串S和T，问在S中是否存在子串，满足T中的所有字符并且不含其它字符

        // 记录窗口中相关字符的出现次数 和 需要凑齐的字符的出现次数
        unordered_map<char, int> window, need;

        for(char c : s1) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= s1.size())
            {
                // 在这里判断是否找到了合法的子串
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return false;
    }
};


// 找到字符串中所有字母异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        unordered_map<char, int> window, need;

        for(char c : p) need[c]++; // 容易忘记 - 注意哦

        int left = 0, right = 0;

        vector<int> res;

        int valid = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= p.size())
            {
                if(valid == need.size())
                    res.push_back(left);

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return res;
    }
};


// 无重复字符的最长子串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0; // 记录结果

        while(right < s.size())
        {
            char c = s[right];

            right++;

            // 进行窗口内数据的一系列更新
            window[c]++;

            // 判断左侧窗口是否要收缩
            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


// 无重复的最长子串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0; // 用于记录结果

        while(right < s.size())
        {
            char c = s[right];

            right++;

            // 进行窗口内数据的一系列更新
            window[c]++;

            while(window[c] > 1) // 说明有重复元素了
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


// 找到字符串中所有字母异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        unordered_map<char, int> window, need;

        for(char c : p) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        vector<int> res; // 用于记录结果

        while(right < s.size())
        {
            char c = s[right];

            right++;

            // 进行窗口内数据的一系列更新
            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= p.size())
            {
                if(valid == need.size())
                    res.push_back(left);

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return res;
    }
};


// 字符串的排列
class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        unordered_map<char, int> window, need;

        for(char c : s1) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return false;
    }
};


// 最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        unordered_map<char, int> window, need;

        for(char c : t) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(valid == need.size())
            {
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};
// class Solution {
// public:
//     string minWindow(string s, string t) 
//     {
//         // need和window相当于计数器，分别记录
//         // T中字符出现次数 和 窗口中相应字符的出现次数
//         unordered_map<char, int> window, need;// 记录窗口的字符和需要凑齐的字符
//         for (char c : t) need[c]++;

//         int left = 0, right = 0;
//         // valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T
//         int valid = 0;
//         // 记录最小覆盖子串的起始索引及长度
//         int start = 0, len = INT_MAX;
//         while (right < s.size()) 
//         {
//             // c是 将移入窗口的字符
//             char c = s[right];
//             // 扩大窗口
//             right++;
//             // 进行窗口内数据的一系列更新
//             if (need.count(c)) 
//             {
//                 window[c]++;
//                 if (window[c] == need[c])
//                     valid++;
//             }

//             // 判断左侧窗口是否要收缩
//             while (valid == need.size()) 
//             {
//                 // 在这里更新最小覆盖子串
//                 if (right - left/*左闭右开，right多走一个位置*/ < len) // 这一步很重要，找最优解用的
//                 {
//                     start = left;
//                     len = right - left;
//                 }
//                 // d是 将移出窗口的字符
//                 char d = s[left];
//                 // 缩小窗口
//                 left++;
//                 // 判断左侧窗口是否要收缩
                   // 左侧窗口收缩的条件是valid的值等于need.size（表示窗口中满足条件的字符的出现次数都和T中的一致）
//                 if (need.count(d)) 
//                 {
//                     if (window[d] == need[d])
//                         valid--;
//                     window[d]--;
//                 }                    
//             }
//         }
//         // 返回最小覆盖子串
//         return len == INT_MAX ?
//             "" : s.substr(start, len); // substr()字符截取函数，从start位置开始截取len个字符
//     }

// };


// 滑动窗口算法框架：
void slidingWindow(string s)
{
	unordered_map<char, int> window;
	
	int left = 0, right = 0;

	while(right < s.size())
	{
		char c = s[right];

		right++;

		// 进行窗口内数据的一系列更新
		....
	

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			char d = s[left];

			left++;

			// 进行窗口哦内数据的一系列更新
			....
		}
	}
}



// 滑动窗口算法框架：

void slidingWindow(string s)
{
	// 窗口中相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将要移入窗口的字符
		char c = s[[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将要移出窗口的字符
			char d = s[left];

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}


// 无重复字符的最长子串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        // 记录窗口中相关字符的出现次数
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0; // 用于记录结果

        while(right < s.size())
        {
            // c是 将要移入窗口的字符
            char c = s[right];

            // 增大窗口
            right++;

            // 进行窗口内数据的一系列更新
            window[c]++;

            // 判断左侧窗口是否要收缩
            while(window[c] > 1)
            {
                // d是 将要移出窗口的字符
                char d = s[left];

                // 缩小窗口
                left++;

                // 进行窗口内数据的一系列更新
                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


// 找到字符串中所有字母异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        unordered_map<char, int> window, need;

        for(char c : p) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        vector<int> res; // 用于记录结果

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                    valid++;
            }

            // 什么时候该进行左侧窗口收缩呢？
            while(right - left >= p.size())
            {
                // 窗口符合条件时，记录起始索引
                if(valid == need.size())
                    res.push_back(left);

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return res;
    }
};


// 字符串的排列
class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        unordered_map<char, int> window, need;

        for(char c : s1) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return false;
    }
};


// 最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        unordered_map<char, int> window, need;

        for(char c : t) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(valid == need.size())
            {
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};


// 最长不含重复元素的子字符串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


// 剑指offer - 字符串中的变位词
class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        unordered_map<char, int> window, need;

        for(char c : s1) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return false;
    }
};


// 剑指offer - 字符串中的所有变位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        unordered_map<char, int> window, need;

        for(char c : p) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        vector<int> res; // 用于记录结果

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= p.size())
            {
                if(valid == need.size())
                    res.push_back(left);

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return res;
    }
};


// 剑指offer - 不含重复字符的最长子字符串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


// 剑指offer - 含有所有字符的最短子字符串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        unordered_map<char, int> window, need;

        for(char c : t) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(valid == need.size())
            {
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};



// 滑动窗口算法框架：

void slidingWindow(string s)
{
	// 记录窗口中相关字符的出现次数
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是 将要移入窗口中的字符
		char c = s[right];

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		....

		// 判断左侧窗口是否要收缩
		while(window needs shrink)
		{
			// d是 将要移出窗口的字符
			char d = s[left];
	
			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}


// 剑指offer - 含有所有字符的最短字符串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        unordered_map<char, int> window, need;
        for(char c : t) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(valid == need.size())
            {
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};


// 剑指offer - 不含重复字符的最长子字符串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


// 剑指offer - 字符串中的所有变位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        unordered_map<char, int> window, need;

        for(char c : p) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        vector<int> res; // 用于记录结果

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                {
                    valid++;
                }
            }

            while(right - left >= p.size())
            {
                if(valid == need.size())
                    res.push_back(left);

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return res;
    }
};


// 剑指offer - 字符串中的变位词
class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        unordered_map<char, int> window, need;
        for(char c : s1) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                {
                    valid++;
                }
            }

            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return false;
    }
};


// 三数之和
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        int left = 0, right = nums.size() - 1;

        vector<vector<int>> res; // 用于记录结果

        // 遍历数组中的每个元素，寻找符合条件的二元组
        for(int i = 0; i < nums.size(); i++)
        {
            vector<vector<int>> twoGroups = twoSum(nums, i+1, 0-nums[i]);

            // 将该元素添加到符合条件的二元组中，继而得到三元组
            for(vector<int>& twoGroup : twoGroups)
            {
                twoGroup.push_back(nums[i]);
                res.push_back(twoGroup);
            }

            // 防止第一个元素重复
            while(i < nums.size() - 1 && nums[i] == nums[i + 1]) i++;
        }

        return res;
    }

    vector<vector<int>> twoSum(vector<int>& nums, int start, int target)
    {
        int left = start, right = nums.size() - 1;

        vector<vector<int>> res;

        while(left < right)
        {
            int sum = nums[left] + nums[right];
            int leftNum = nums[left], rightNum = nums[right];

            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else if(sum == target)
            {
                res.push_back({nums[left], nums[right]});

                while(left < right && nums[left] == leftNum)
                    left++;
                while(left < right && nums[right] == rightNum)
                    right--;
            }
        }

        return res;
    }
};


// 四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());

        int left = 0, right = nums.size() - 1;

        vector<vector<int>> res; // 用于记录结果

        // 遍历数组中的每个元素，寻找符合条件的三元组
        for(int i = 0; i < nums.size(); i++)
        {
            vector<vector<int>> threeGroups = threeSum(nums,i+1,target-nums[i]);

            // 将该元素添加大符合条件的三元组中，从而组成四元组
            for(vector<int>& threeGroup : threeGroups)
            {
                threeGroup.push_back(nums[i]);
                res.push_back(threeGroup);
            }

            // 防止第一个元素重复
            while(i < nums.size() - 1 && nums[i] == nums[i+1]) i++;
        }

        return res;
    }

    vector<vector<int>> threeSum(vector<int>& nums, int start, long target) 
    {
        // sort(nums.begin(), nums.end());

        vector<vector<int>> res; // 用于记录结果

        // 遍历数组中的每个元素，寻找符合条件的二元组
        for(int i = start; i < nums.size(); i++)
        {
            vector<vector<int>> twoGroups = twoSum(nums, i+1, target-nums[i]);

            // 将该元素添加到符合条件的二元组中，继而得到三元组
            for(vector<int>& twoGroup : twoGroups)
            {
                twoGroup.push_back(nums[i]);
                res.push_back(twoGroup);
            }

            // 防止第一个元素重复
            while(i < nums.size() - 1 && nums[i] == nums[i + 1]) i++;
        }

        return res;
    }

    vector<vector<int>> twoSum(vector<int>& nums, int start, int target)
    {
        int left = start, right = nums.size() - 1;

        vector<vector<int>> res;

        while(left < right)
        {
            int sum = nums[left] + nums[right];
            int leftNum = nums[left], rightNum = nums[right];

            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else if(sum == target)
            {
                res.push_back({nums[left], nums[right]});

                while(left < right && nums[left] == leftNum)
                    left++;
                while(left < right && nums[right] == rightNum)
                    right--;
            }
        }

        return res;
    }
};




void slidingWindow(string s)
{
	unordered_map<char, int> window; 
	int left = 0, right = 0;

	while(right < s.size())
	{
		char c = s[right];

		right++;

		// 进行窗口内数据的一系列更新
		....

		while(window needs shrink)
		{
			char d = s[left];

			left++;

			// 进行窗口内数据的一系列更新
			....
		}
	}
}



// 剑指offer - 含有所有字符的最短字符串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        unordered_map<char, int> window, need;

        for(char c : t) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                    valid++;
            }

            while(valid == need.size())
            {
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];
                
                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};



// 剑指offer - 不含在重复字符的最长子字符串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};



// 剑指offer - 字符串中的所有变位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        unordered_map<char, int> window, need;

        for(char c : p) need[c]++;

        vector<int> res;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= p.size())
            {
                if(valid == need.size())
                    res.push_back(left);

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return res;
    }
};



// 剑指offer - 字符串中的变位词
class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        unordered_map<char, int> window, need;
        for(char c : s1) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                {
                    valid++;
                }
            }

            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        valid--;
                    }

                    window[d]--;
                }
            }
        }

        return false;
    }
};



// 剑指offer - 最长不含重复字符的子字符串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d =s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};



// 剑指offer - 含有所有字符的最短字符串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        unordered_map<char, int> window, need;
        for(char c : t) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        // 最小子串的起始位置和长度
        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                    valid++;
            }

            while(valid == need.size())
            {
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }

            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};



// 剑指offer - 不含重复字符的最长子字符串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};



// 剑指offer - 字符串中的变位词
class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        unordered_map<char, int> window, need;
        for(char c : s1) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return false;
    }
};



// 剑指offer - 最长不含重复字符的子字符串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};



// 滑动窗口框架
void slidingWindow(string s)
{
	// 用合适的数据结构记录窗口中的数据
	unordered_map<char, int> window;

	int left = 0, right = 0;

	while(right < s.size())
	{
		// c是将移入窗口的字符
		char c = s[right];
		window.add(c);

		// 增大窗口
		right++;

		// 进行窗口内数据的一系列更新
		...

		printf("window: [%d : %d)\n", left, right);

		// 判断左侧窗口是否要收缩
		while(left < right && window needs shrink)
		{
			// d是将移出窗口的字符
			char d = s[left];

			window.remove(d);

			// 缩小窗口
			left++;

			// 进行窗口内数据的一系列更新
			...
		}
	}
}



		class Solution {
public:
    string minWindow(string s, string t) 
    {
        // 记录窗口中相关字符的出现次数 和 需要凑齐的字符出现次数
        unordered_map<char, int> window, need;

        for(char c : t)
            need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        // 记录最小覆盖子串的起始索引和长度
        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];

            // 扩大窗口
            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                {
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while(valid == need.size())
            {
                // 更新最小覆盖子串
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                // 缩小窗口
                left++;

                // 进行窗口内数据的一系列更新
                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        valid--;
                    }
                    window[d]--;
                }
                
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

class Solution {
public:
    string minWindow(string s, string t) 
    {
        // 记录窗口中相关字符的出现次数 和 需要凑齐的字符的出现次数
        unordered_map<char, int> window, need;

        for(char c : t)
            need[c]++;

        int left = 0, right = 0; //记录窗口的边界

        int valid = 0;

        int start = 0, len = INT_MAX; // 记录最小覆盖子串的起始位置和长度

        while(right < s.size())
        {
            char c = s[right];

            // 扩大窗口
            right++;

            // 进行窗口内数据的一系列更新
            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                {
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while(valid == need.size())
            {
                // 更新最小覆盖子串
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                // 收缩窗口
                left++;

                // 进行窗口内数据的一系列更新
                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        valid--;
                    }

                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};


class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        // 记录窗口中相关字符的出现次数
        unordered_map<char, int> window;

        int left = 0, right = 0;

        // 记录结果
        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            // 扩大窗口
            right++;

            window[c]++;

            // 判断左侧窗口是否要收缩
            while(window[c] > 1)
            {
                char d = s[left];

                // 缩小窗口
                left++;

                // 进行窗口内数据的一系列更新
                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        // 记录窗口中相关字符的出现次数 和 需要凑齐的字符的出现次数
        unordered_map<char, int> window, need;

        for(char c : p)
            need[c]++;

        // 用于记录结果
        vector<int> res;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s.size())
        {
            char c = s[right];

            // 扩大窗口
            right++;

            // 进行窗口内数据的一系列更新
            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                {
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while(right - left >= p.size())
            {
                if(valid == need.size())
                    res.push_back(left);

                char d = s[left];

                // 缩小窗口
                left++;

                // 进行窗口内数据的一系列更新
                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        valid--;
                    }

                    window[d]--;
                }
            }
        }
        return res;
    }
};


class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        // 记录窗口中相关字符的出现次数 和 需要凑齐的字符出现次数
        unordered_map<char, int> window, need;

        for(char c : s1)
            need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            // 扩大窗口
            right++;

            // 进行窗口内数据的一系列更新
            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            // 判断左侧窗口是否要收缩
            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                // 缩小窗口
                left++;

                // 进行窗口内数据的一系列更新
                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        valid--;
                    }

                    window[d]--;
                }
            }
        }

        return false;
    }
};


class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int res = 0;

        int left = 0, right = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        unordered_map<char, int> window, need;

        for(char c : s1)
            need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return false;
    }
};

class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        unordered_map<char, int> window, need;

        for(char c : p)
            need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        vector<int> res;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= p.size())
            {
                if(valid == need.size())
                    res.push_back(left);

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return res;
    }
};


class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


class Solution {
public:
    string minWindow(string s, string t) 
    {
        unordered_map<char, int> window, need;

        for(char c : t)
        {
            need[c]++;
        }

        int left = 0, right = 0;

        int valid = 0;

        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(valid == need.size())
            {
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};


class Solution {
public:
    string minWindow(string s, string t) 
    {
        // 记录和窗口中元素的出现次数 和 需要凑齐的字符的出现次数
        unordered_map<char, int> window, need;

        for(auto& e : t)
            need[e]++;

        int left = 0, right = 0;

        // 记录最小覆盖子串的起始地址和长度
        int start = 0, len = INT_MAX;

        int valid = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(valid == need.size())
            {
                // 更新最小覆盖子串
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

	
